package bishi.kaizi;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2022/03/26 15:12
 */
public class _14 {
    public static void main(String[] args) {
        _14 one = new _14();
        System.out.println(Arrays.toString(one.getTreasures(6,10,new int[][]{{1, 2, 4, 3}, {2, 3, 2, 2}, {3, 4, 1, 4}})));
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * <p>
     * 求在魔王苏醒之前，可以获取到价值最高的宝物列表；
     *
     * @param packageSize  int整型 背包容量
     * @param wakeTime     int整型 魔王睡醒时长
     * @param treasureInfo int整型二维数组 宝物信息数组；宝物信息数组；[[宝物id, 宝物距离, 宝物重量, 宝物价值]]
     * @return int整型一维数组
     */
    int max = 0;
    int[] res = null;
    public int[] getTreasures(int packageSize, int wakeTime, int[][] treasureInfo) {
        // write code here
        List<Integer> list = new ArrayList<>();
        int now = 0;
        dfs(packageSize, wakeTime, treasureInfo, 0, list, now);
        return res;
    }

    public void dfs(int packageSize, int wakeTime, int[][] treasureInfo, int index, List<Integer> list, int now) {
        for (int i = index; i < treasureInfo.length; i++) {
            if (treasureInfo[i][2] <= packageSize && treasureInfo[i][1] + 1 <= wakeTime) {
                list.add(i);
                now += treasureInfo[i][3];
                dfs(packageSize - treasureInfo[i][2], wakeTime - treasureInfo[i][1] - 1, treasureInfo, i + 1, list, now);
                list.remove(list.size() - 1);
                now -= treasureInfo[i][3];
            }
        }
        if (now > max) {
            max = now;
            res = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                res[i] = list.get(i) + 1;
            }
        }
    }
}
